1642. Домашнее задание

Коля по-прежнему пытается пройти тест по теории чисел. Лектор настолько доведен до отчаяния знаниями Коли, что она дает ему каждый раз одну и ту же задачу.

В задаче следует проверить, делится ли n! на n².

Вход. Одно число n (1 ≤ n ≤ 10⁹).

Выход. Вывести “YES”, если n! делится на n². Иначе вывести “NO”.

Пример входа	Пример выхода
3	NO

РЕШЕНИЕ

тест на простоту

Анализ алгоритма

Поскольку n! = 1 * 2 * … * n, то n! делится на n. Если n простое, то произведение n! / n = 1 * 2 * … * (n – 1) не делится на n. Следовательно при простом n значение n! не делится на n².

Если n не простое, то его можно представить в виде произведения двух чисел (не обязательно простых): например n = a * b. Тогда n! = (a * b)! содержит множители a, b, a * b и n! делится на n².

Отдельно рассмотрим два случая:

· при n = 1 (не простое и не составное) значение n! делится на n²;

· при n = 4 (составное) значение n! не делится на n².

Пример

Если n = 5 (простое), то 5! = 1 * 2 * 3 * 4 * 5 не делится на 5².

Если n = 15 (составное), то 15! в своем разложении содержит множители 3, 5 и 15, и следовательно делится на 15².

Если n = 4 (составное), то 4! = 1 * 2 * 3* 4 делится на 4, но не делится на 4².

Реализация алгоритма

Функция IsPrime проверяет, является ли число n простым. Если n простое, то функция возвращает 1. Иначе функция возвращает 0.

int IsPrime(int n)

{

for(int i = 2; i <= sqrt(1.0*n); i++)

if (n % i == 0) return 0;

return 1;

}

Основная часть программы. Читаем входное значение n.

scanf("%d",&n);

Выводим ответ в зависимости от значения n.

if (n == 4) puts("NO"); else

if (n == 1 || !IsPrime(n)) puts("YES");

else puts("NO");

Java реализация

import java.util.*;

public class Main

{

public static boolean IsPrime(int n)

{

for(int i = 2; i <= Math.sqrt(n); i++)

if (n % i == 0) return false;

return true;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

if (n == 4) System.out.println("NO"); else

if (n == 1 || !IsPrime(n)) System.out.println("YES");

else System.out.println("NO");

con.close();

}

}

Python реализация

import math

def IsPrime(n):

for i in range(2, int(math.sqrt(n))+1):

if n % i == 0: return False

return True

n = int(input())

if n == 4:

print("NO")

elif n == 1 or not IsPrime(n):

print("YES")

else:

print("NO");